package com.cty.C_SortAlgorithms.H_RadixSort;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/18 18:13
 * @Description: 基数排序
 * @version: 1.0
 */
public class RadixSort {
    private int maxSize;
    private DataItem[] array;
    private int nItems;
    private final int MAXSIZE = 10;
    private QueueChain[] queues;

    public RadixSort(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
        queues = new QueueChain[MAXSIZE];
        for(int i=0; i<MAXSIZE; i++)
            queues[i] = new QueueChain();
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems++] = item;
        return true;
    }

    public void setArray(DataItem[] array){
        this.array = array;
        nItems = array.length;
    }

    /**
     * 基数排序
     *      平均时间复杂度：  O(N*logN)         受数据分布影响较小
     *      最好情况：        O(N*logN)
     *      最坏情况：        O(N*logN)
     *      空间复杂度：      >O(N) <O(k*N)
     *      排序方式：                         外部排序
     *      稳定性：                           稳定
     * 分析：
     *      基数排序主要是复制次数：2*N*⌊log r(N)⌋    （其中r是基数）
     *          数据关键字最大是 k 位数就需要循环 k 次，每次循环都需要 2*N 次复制：
     *              第一次是将全部数据项从数字数组复制到队列数组
     *              第二次是将全部数据项从队列数组复制到数字数组
     *          数据关键字最大位数 k 与数据项个数 N 之间的关系是 k = ⌊log r(N)⌋
     */
    public void radixSort(int figure){
        int curFigure = 1;  // 1-个位  2-十位  3-百位  ...

        while(curFigure <= figure){
            // 将数据从数据数组移到队列数组
            for(int i=0; i<nItems; i++){
                String keyStr = array[i].getKey() + "";  // 将当前数据项关键字转化成字符串
                int keyLen = keyStr.length();  // 获取当前数据项关键字位数

                if(keyLen < curFigure)  // 若当前数据项关键字位数小于当前处理位数
                    queues[0].insert(array[i]);  // 按0来处理
                else
                    queues[keyStr.charAt(keyLen-curFigure)-'0'].insert(array[i]);  // 按该位的数值来处理
            }  // end for

            // 将数据从哪队列数组移到数据数组
            int j = 0;
            for(int i=0; i<10; i++)
                while(!queues[i].isEmpty())
                    array[j++] = queues[i].remove();

            // 更新判断条件
            curFigure++;
        }  // end while
    }  // end radixSort()

}  // end RadixSort{}

/**
 * 41 38 15 77 9 60 26 34 13 53
 * 9 13 15 26 34 38 41 53 60 77
 */
